The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also be inventions.
A database system may use market basket analysis to create association rules in the form of X→Y, where X and Y are disjoint sets of items. Such association rules may be used for making recommendations based on a sufficiently high confidence P(Y|X), which has the interpretation “the probability of Y given X i.e., of the transactions in which at least all of the items in X were purchased, in P(Y|X) of them all the items in Y were also purchased.” A high confidence association rule may be used to recommend Y when a user purchases X in the same ecommerce basket or shopping cart. However, even when a database system has basket data available, some basket sizes may be much larger than basket sizes used in typical ecommerce settings. For example, a user may purchase the information for several thousand business contacts in a single transaction, in contrast to typical ecommerce shopping baskets which usually contain less than 30 items. Working with very large basket sizes substantially increases the computational complexity of market basket analysis. Even a fast algorithm slows down immensely on large baskets because even if the database system seeks association rules X→Y in which |X| is small, such as n=3, a basket of size m has “m choose n” subsets of cardinality n each, each of which necessarily has to be enumerated.